package leetcode.栈队列堆;

/**
 * 寻找两个有序数组的中位数
 *
 * 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
 *
 * 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 *
 * 你可以假设 nums1 和 nums2 不会同时为空。
 *
 * 示例 1:
 *
 * nums1 = [1, 3]
 * nums2 = [2]
 *
 * 则中位数是 2.0
 * 示例 2:
 *
 * nums1 = [1, 2]
 * nums2 = [3, 4]
 *
 * 则中位数是 (2 + 3)/2 = 2.5
 */
public class Test4寻找两个有序数组的中位数 {

    /*
     第二种解法：构造大顶堆和小顶堆
     中位数一定在排序数组的中间，但是我们不用真正的排序，
     中位数的特点是：左边的小于他，右边的大于他
     所以构建大顶堆放到左边，构造小顶堆放到右边
     最后取堆顶元素计算均值即可
      */

    // 第一种解法：暴力
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] newArray = new int[nums1.length + nums2.length];
        for (int i = 0; i < newArray.length; ) {
            for (int j = 0; j < nums1.length; j++,i++) {
                newArray[i] = nums1[j];
            }
            for (int k = 0; k < nums2.length; k++,i++) {
                newArray[i] = nums2[k];
            }
        }
        shellSort(newArray);

        return getMid(newArray);
    }

    public static void shellSort(int[] a) {
        int n = a.length;
        // 设置增量，增量的取法有很多，这里是推荐取法
        int h = 1;
        while (h < n / 3) {
            h = 3 * h + 1;
        }
        // 增量最小为 1 ，也就是相邻的两个元素比较
        while (h >= 1) {

            // 对相聚 h 的两个元素插入排序
            for (int i = h; i < n; i++) {
                for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {
                    exch(a, j, j-h);
                }
            }
            // 排序结束后，缩小增量，继续排序
            h /= 3;
        }
    }
    private static void exch(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    private static boolean less(Comparable v, Comparable w) {
        // 若 v 小于 w 则返回负数
        return v.compareTo(w) < 0;
    }
    public static double getMid(int[] a) {
        if (a.length % 2 == 0) {
            return (a[ a.length / 2] + a[ a.length / 2 - 1]) / 2.0;
        } else {
            return (a[ a.length / 2]);
        }
    }

}
